package leetcode_2101_2200;

public class LeeCode_2106 {
    public static void main(String[] args) {
//        System.out.println(maxTotalFruits(new int[][]{{2, 8}, {6, 3}, {8, 6}}, 5, 4));
        System.out.println(maxTotalFruits(new int[][]{{0, 9}, {4, 1}, {5, 7},{6, 2},{7,4},{10,9}}, 5, 4));
    }
    private static int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] += sums[i - 1] + fruits[i - 1][1];
        }
        int l = startPos - k, r = startPos, ans = 0;
        while (l <= startPos){
            int s = search2(fruits, l);
            int e = search(fruits, r);
            int res = sums[e + 1] - sums[s + 1];
            ans = Math.max(res, ans);
            l += 2;
            r++;
        }
        r = startPos + k;
        l = startPos;
        while (r >= startPos){
            int s = search2(fruits, l);
            int e = search(fruits, r);
            int res = sums[e + 1] - sums[s + 1];
            ans = Math.max(res, ans);
            r -= 2;
            l--;
        }
        return ans;
    }
    private static int search2(int[][] fruits, int i){
        int n = fruits.length;
        int l = 0, r = n - 1;
        while(l < r){
            int m = (l + r + 1) / 2;
            if(fruits[m][0] < i){
                l = m;
            }else{
                r = m - 1;
            }
        }
        if(fruits[l][0] >= i){
            return -1;
        }
        return l;
    }
    private static int search(int[][] fruits, int i){
        int n = fruits.length;
        int l = 0, r = n - 1;
        while(l < r){
            int m = (l + r + 1) / 2;
            if(fruits[m][0] <= i){
                l = m;
            }else{
                r = m - 1;
            }
        }
        if(fruits[l][0] > i){
            return -1;
        }
        return l;
    }
}
